package BinaryTree;//给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
//
// 
// 二叉树的根是数组 nums 中的最大元素。 
// 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 
// 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 
// 
//
// 返回有给定数组 nums 构建的 最大二叉树 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,1,6,0,5]
//输出：[6,3,5,null,2,0,null,null,1]
//解释：递归调用如下所示：
//- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//        - 空数组，无子节点。
//        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//            - 空数组，无子节点。
//            - 只有一个元素，所以子节点是一个值为 1 的节点。
//    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//        - 只有一个元素，所以子节点是一个值为 0 的节点。
//        - 空数组，无子节点。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[3,null,2,null,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 1000 
// nums 中的所有整数 互不相同 
// 
// Related Topics 栈 树 数组 分治 二叉树 单调栈 👍 342 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Arrays;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class constructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        /**
         * 首先确定数组中的最大值的位置，然后划分左右数组
         * */

        return build(nums, 0, nums.length);
    }

    TreeNode build(int[] Nums, int leftIndex, int rightIndex){
        /**
         * 自己写的时候对于左右数组截取这部分陷入误区，
         * 以为还要根据最大值位置 来截取两边数组
         * 但其实保持原数组不变，每次传新数组的开始结束位置，就可以实现
         *
         * */
        int len = Nums.length;
        //如果当前数组为空，说明已经到空节点
        if (rightIndex - leftIndex < 1){
            return null;
        }
        if(rightIndex - leftIndex == 1){
            //如果到最后构建节点
            return new TreeNode(Nums[leftIndex]);
        }
        //初始化最大值和下标，并找当前的最大值和下标
        int index = leftIndex;
        int max = Nums[index];
        for (int i = leftIndex+1; i < rightIndex; i++) {
            if(Nums[i] > max){
                index = i;
                max = Nums[i];
            }
        }
        //以当前最大值节点构建节点
        TreeNode root = new TreeNode(Nums[index]);

        //如果最大值左边没有元素，没必要构建左边
        root.left = build(Nums, leftIndex, index);
        root.right = build(Nums, index+1, rightIndex);

        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
